We revisit the problem of designing optimal, individually rational matchingmechanisms (in a general sense, allowing for cycles in directed graphs), whereeach player --- who is associated with a subset of vertices --- matches as manyof his own vertices when he opts into the matching mechanism as when he optsout. We offer a new perspective on this problem by considering an arbitrarygraph, but assuming that vertices are associated with players at random. Ourmain result asserts that, under certain conditions, any fixed optimal matchingis likely to be individually rational up to lower-order terms. We also showthat a simple and practical mechanism is (fully) individually rational, andlikely to be optimal up to lower-order terms. We discuss the implications ofour results for market design in general, and kidney exchange in particular.
展开▼
